/** 
 * Solver.java
 * PROJECT 3: Sliding Block Puzzle Solver
 * @author Jonathan Kotker	cs61b-ar
 * @author Wei Zhong Yeh	cs61b-av
 * 
 * Path finding class. Named "The" since it is *the* class with the most important task.
 */

import java.util.*;

public class The {

	private Stack <Tray> myOpen;
	private HashSet <Tray> myClosed;
	private Goal myGoalConfig;
	private Integer myTrayLength;
	private Integer myTrayWidth;
	// for debugging purposes
	private static boolean contentsOfSetsFlag = false;
	private static boolean blockMovementFlag = false;
	private static boolean trayViewFlag = false;
	private static boolean movementStatisticsFlag = false;
	private static int movements = 0;
	private static int trayNumber = 0;
	private static long totalMovementTime = 0;
	
	public The ( ) {
		this (0, 0, new Tray ( ), new Goal ( ));
	}

	/**
	 * Constructor to construct The in order to find the path from the initialConfig tray to the goalConfig tray
	 * @param length			length of tray
	 * @param width				width of tray
	 * @param initialConfig		initial tray
	 * @param goalConfig		goal tray
	 */
	public The (Integer length, Integer width, Tray initialConfig, Goal goalConfig) {
		this.myOpen = new Stack <Tray> ( );
		this.myOpen.push (initialConfig);
		this.myClosed = new HashSet <Tray> ( );
		this.myGoalConfig = goalConfig;
		this.myTrayLength = length;
		this.myTrayWidth = width;
	}

	/**
	 * 
	 * @return LinkedList containing the solution
	 */
	public LinkedList <int [ ]> findSolution ( ) {
		// temporary variable to store Trays, as received
		Tray currentTray;
		// temporary variables to store the result tray, and to signal that a result has been found
		Tray resultTray = new Tray ( );
		boolean solutionFound = false;
		
		// for debugging purposes
		// keep track of the shortest and longest time taken to generate a move
		long shortestMovementTime = 100;
		long longestMovementTime = 0;
		Timer moverTimer = new Timer ( );
		Timer solutionTimer = new Timer ( );
		// start the timer to calucluate the amount of time in which a solution is found
		if (movementStatisticsFlag) {
			solutionTimer.start ( );
		}
		
		// keep removing Trays from myOpen until it is empty, at which point the method fails
		while (! this.myOpen.empty ( )) {
			// System.out.println ("myOpen: " + myOpen.size());
			// System.out.println ("myClosed: " + myClosed.size());
			currentTray = this.myOpen.pop ( );
			trayNumber++;
			
			// debugging output
			if (contentsOfSetsFlag) {
				Debug.debugPrint ("*** Tray number " + trayNumber + " ***");
				Debug.debugPrint ("There are still " + myOpen.size ( ) + " trays to be considered.");
				Debug.debugPrint ("There are, however, " + myClosed.size ( ) + " trays that have been already seen.");
				Debug.debugPrint ("***");
				Debug.debugPrint ("");
			}

			if (trayViewFlag) {
				// temporary variable to store how this tray was generated
				int [ ] blockMove = currentTray.getBlockMove ( );
				Debug.debugPrint ("*** Tray number " + trayNumber + " ***");
				Debug.debugPrint ("The tray currently being examined is ");
				Debug.debugPrint (currentTray.toString ( ));
				// Debug.debugPrint ("Its heuristic is " + currentTray.getHeuristic ( ));
				Debug.debugPrint ("It was generated by moving the block at (" + blockMove [0] + ", " + blockMove [1] + ") to (" + blockMove [2] + ", " + blockMove [3] + ")");
				Debug.debugPrint ("***");
				Debug.debugPrint ("");
			}
			
			// add the tray removed from myOpen to the collection of trays already examined
			this.myClosed.add (currentTray);

			// temporary variables to iterate through the tray taken, and store the trays and blocks received 
			Iterator <Block> blocks = currentTray.blockIterator ( );
			Tray tempTray;
			Block tempBlock;
			
			// move each block, making sure not to confuse the Block to be moved with itself
			while (blocks.hasNext ( ) && !solutionFound) {
				tempBlock = blocks.next ( );
				// try moving currentBlock in every possible direction and add the resultant tray to myOpen
				for (int i = 0; i < 4; i++) {
					moverTimer.start ( );
					tempTray = this.tryMove (tempBlock, currentTray, (byte) i);
					moverTimer.stop ( );
					
					// for debugging output
					if (movementStatisticsFlag) {
						if (moverTimer.elapsed ( ) < shortestMovementTime)
							shortestMovementTime = moverTimer.elapsed ( );
						if (moverTimer.elapsed ( ) > longestMovementTime)
							longestMovementTime = moverTimer.elapsed ( );
					}

					if (tempTray != null) {
						movements ++;
						// check if goal has been reached
						if (this.myGoalConfig.goalReached (tempTray)) {
							resultTray = tempTray;
							solutionFound = true;
						}
						// before adding to myOpen, make sure tempTray has not already been seen
						else if (!this.myClosed.contains (tempTray)) {
							this.myOpen.push (tempTray);
						}
					}
				}
			}
		}
		
		if (movementStatisticsFlag) {
			solutionTimer.stop ( );
			
			// calculate necessary statistics
			totalMovementTime = solutionTimer.elapsed ( );
			long timePerMovement = totalMovementTime / movements;
			Debug.debugPrint ("*** SOLUTION STATISTICS ***");
			Debug.debugPrint ("(All time is in milliseconds)");
			Debug.debugPrint ("Time required to find solution: " + totalMovementTime);
			Debug.debugPrint ("Number of movements conducted: " + movements);
			Debug.debugPrint ("Average time per movement: " + timePerMovement);
			Debug.debugPrint ("Longest time taken for movement: " + longestMovementTime);
			Debug.debugPrint ("Shortest time taken for movement: " + shortestMovementTime);
			Debug.debugPrint ("***");
		}
		
		if (solutionFound) {
			return Tray.finalSolution (resultTray);
		} else {
			System.exit (1);
			return null;
		}
	}
	
	/**
	 * Tries to move a Block in the specified direction moveWhere
	 * @param currentBlock Block to be moved
	 * @param currentTray  Tray to move with respect to
	 * @param moveWhere	   Which direction to move (0 = up, 1 = down, 2 = left, 3 = right)
	 * @return	Tray resulting from moving one Block in one direction by one unit or null if not moveable
	 */
	private Tray tryMove2 (Block currentBlock, Tray currentTray, byte moveWhere) {
		Block futureBlock = null;
		List <Block> otherBlocks = null;
		if (moveWhere == 0) {
			futureBlock = currentBlock.moveUp (myTrayLength, myTrayWidth);
			otherBlocks = currentTray.getSortedBlocks ( ).getMoveUpBlocks (currentBlock);
		} else if (moveWhere == 1) {
			futureBlock = currentBlock.moveDown (myTrayLength, myTrayWidth);
			otherBlocks = currentTray.getSortedBlocks ( ).getMoveDownBlocks (currentBlock);
		} else if (moveWhere == 2) {
			futureBlock = currentBlock.moveLeft (myTrayLength, myTrayWidth);
			otherBlocks = currentTray.getSortedBlocks ( ).getMoveLeftBlocks (currentBlock);
		} else if (moveWhere == 3) {
			futureBlock = currentBlock.moveRight (myTrayLength, myTrayWidth);
			otherBlocks = currentTray.getSortedBlocks ( ).getMoveRightBlocks (currentBlock);
		}
		// if futureBlock is 'null', it means futureBlock has ran outside of the tray
		if (futureBlock == null) {
			return null;
		}

		Block tempBlock;
		boolean intersects = false;
		for (int i = 0; i < otherBlocks.size ( ); i++) {
			tempBlock = otherBlocks.get (i);
			if (tempBlock != currentBlock && tempBlock.intersectsWith (futureBlock))
				intersects = true;
		}		
		
		if (intersects) {
			return null;
		} else {
			return new Tray (currentTray, currentBlock, futureBlock, myGoalConfig);
		}
	}

	/**
	 * Tries to move a Block in the specified direction moveWhere
	 * @param 	currentBlock 		block to be moved
	 * @param 	currentTray  		tray to move with respect to
	 * @param 	moveWhere	   		which direction to move (0 = up, 1 = down, 2 = left, 3 = right)
	 * @return	Tray resulting 		from moving one Block in one direction by one unit or null if not moveable
	 */
	private Tray tryMove (Block currentBlock, Tray currentTray, byte moveWhere) {
		// for debugging
		if (blockMovementFlag)
			currentBlock.trackMovement ( );
		
		Block futureBlock = null;
		if (moveWhere == 0)
			futureBlock = currentBlock.moveUp (this.myTrayLength, this.myTrayWidth);
		else if (moveWhere == 1)
			futureBlock = currentBlock.moveDown (this.myTrayLength, this.myTrayWidth);
		else if (moveWhere == 2)
			futureBlock = currentBlock.moveLeft (this.myTrayLength, this.myTrayWidth);
		else if (moveWhere == 3)
			futureBlock = currentBlock.moveRight (this.myTrayLength, this.myTrayWidth);
		// if futureBlock is 'null', it means that the futureBlock has ran outside of the tray
		if (futureBlock == null)
			return null;

		Iterator <Block> blocks = currentTray.blockIterator ( );
		Block tempBlock;
		boolean intersects = false;

		// check for intersections
		while (blocks.hasNext ( ) && intersects == false) {
			tempBlock = blocks.next ( );
			if (tempBlock != currentBlock && tempBlock.intersectsWith (futureBlock))
				intersects = true;
		}
		
		if (intersects)
			return null;
		else	
			// return the tray resulting from the movement of one block
			return new Tray (currentTray, currentBlock, futureBlock, myGoalConfig);
	}
	
	/**
	 * Set the boolean flag that outputs the number of Trays in the myOpen and myClosed collections
	 */
	public static void displayContentsOfSet ( ) {
		contentsOfSetsFlag = true;
	}
	
	/**
	 * Set the boolean flag that outputs the tray currently being examined
	 */
	public static void viewChosenTrays ( ) {
		trayViewFlag = true;
	}
	
	/**
	 * Set the boolean flag that provides the collated statistics of all block movements
	 */
	public static void findMovementStatistics ( ) {
		movementStatisticsFlag = true;
	}
	
	/**
	 * Set the boolean flag that tracks the movement of a singular block
	 */
	public static void trackMovement ( ) {
		blockMovementFlag = true;
	}
}